package all;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author zhang lei
 * @Date 2022-01-21 17:25
 */
public class Test50TO100 {
    public static void main(String[] args) {
        System.out.println(uniquePaths(3,7));
    }


    /**
     * 62 不同路径
     * @param m
     * @param n
     *
     * f(i, j) = f(i-1, j) + f(i, j-1);
     * @return
     */
    private static Map<String, Integer> map = new HashMap<>();
    public static int uniquePaths(int m, int n) {
//        return path(m-1, n-1);
        int[] arr = new int[n];
        arr[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(i == 0) {
                    arr[j] = 1;
                }else {
                    arr[j] = arr[j] + arr[j-1];
                }
            }
        }
        return arr[n-1];
    }

    private static Integer path(int m, int n) {
        String key = m+","+n;
        if(map.get(key)!=null) {
            return map.get(key);
        }
        Integer result;
        if(m == 0 || n==0) {
            result = 1;
        }else {
            result = path(m - 1, n) + path(m, n - 1);
        }
        map.put(key, result);
        return result;
    }
}
